package leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class LeetCode138 {

    //返回头结点
    public Node copyRandomList1(Node head) {
        Node p = head;
        Node result = new Node(-1), q = result;
        while (p != null) {
            Node tmp = new Node(p.val);
            tmp.random = helperRandom1(p);
            q.next = tmp;
            q = q.next;
            p = p.next;
        }
        return result.next;
    }

    private Node helperRandom1(Node node) {
        if (node == null)
            return null;
        Node tmp = new Node(node.val);
        tmp.random = helperRandom1(tmp.random);
        return tmp;
    }
//------------------------------------------------------------------

    Map<Node, Node> newToOldMap = new HashMap<>();
    Map<Node, Node> oldToNewMap = new HashMap<>();

    public Node copyRandomList(Node head) {
        Node p = head;
        Node result = new Node(-1), q = result;
        while (p != null) {
            Node newNode = new Node(p.val);
            q.next = newNode;
            newToOldMap.put(newNode, p);
            oldToNewMap.put(p, newNode);
            p = p.next;
            q = q.next;
        }
        q = result.next;
        while (q != null) {
            helperRandom(q);
            q = q.next;
        }
        return result.next;
    }

    private void helperRandom(Node newNode) {
        Node oldNode = newToOldMap.get(newNode);
        Node oldNodeRandom = oldNode.random;
        newNode.random = oldToNewMap.get(oldNodeRandom);
    }
}
